首先有一个结论:
g c d ( i ⋅ j , i ⋅ k , j ⋅ k ) = g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) g c d ( i , j , k ) gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}
g c d ( i ⋅ j , i ⋅ k , j ⋅ k ) = g c d ( i , j , k ) g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k )
证明如下:
先将 i , j , k i,j,k i , j , k 用唯一分解定理展开的次方分别为 w 1 , w 2 , w 3 w_1,w_2,w_3 w 1 , w 2 , w 3 。
g c d ( i ⋅ j , j ⋅ k , i ⋅ k ) = ∑ i = 1 k p i m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i ) gcd(i \cdot j,j \cdot k,i \cdot k)=\sum_{i=1}^k {p_i}^{min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}
g c d ( i ⋅ j , j ⋅ k , i ⋅ k ) = i = 1 ∑ k p i m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i )
g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) = ∑ i = 1 k p i m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i ) gcd(i,j) \cdot gcd(j,k) \cdot gcd(i,k)=\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})}
g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) = i = 1 ∑ k p i m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i )
g c d ( i , j , k ) = ∑ i = 1 k p i m i n ( w 1 i , w 2 i , w 3 i ) gcd(i,j,k)=\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i},w_{3i})}
g c d ( i , j , k ) = i = 1 ∑ k p i m i n ( w 1 i , w 2 i , w 3 i )
g c d ( i ⋅ j , i ⋅ k , j ⋅ k ) = g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) g c d ( i , j , k ) gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}
g c d ( i ⋅ j , i ⋅ k , j ⋅ k ) = g c d ( i , j , k ) g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k )
⇐ ∑ i = 1 k p i m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i ) = ∑ i = 1 k p i m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i ) ∑ i = 1 k p i m i n ( w 1 i , w 2 i , w 3 i ) \Leftarrow \sum_{i=1}^k {p_i}^{min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}=\frac{\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})}}{\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i},w_{3i})}}
⇐ i = 1 ∑ k p i m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i ) = ∑ i = 1 k p i m i n ( w 1 i , w 2 i , w 3 i ) ∑ i = 1 k p i m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i )
⇐ ∑ i = 1 k m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i ) = ∑ i = 1 k m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i ) − m i n ( w 1 i , w 2 i , w 3 i ) \Leftarrow \sum_{i=1}^k {min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}=\sum_{i=1}^k {min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})-min(w_{1i},w_{2i},w_{3i})}
⇐ i = 1 ∑ k m i n ( w 1 i + w 2 i , w 2 i + w 3 i , w 1 i + w 3 i ) = i = 1 ∑ k m i n ( w 1 i , w 2 i ) + m i n ( w 2 i , w 3 i ) + m i n ( w 1 i , w 3 i ) − m i n ( w 1 i , w 2 i , w 3 i )
这是一个轮换式 , 不妨令 w 1 i ≤ w 2 i ≤ w 3 i w_{1i} \le w_{2i} \le w_{3i} w 1 i ≤ w 2 i ≤ w 3 i , 则有
⇐ ∑ i = 1 k w 1 i + w 2 i = ∑ i = 1 k w 1 i + w 2 i + w 1 i − w 1 i \Leftarrow \sum_{i=1}^k {w_{1i}+w_{2i}}=\sum_{i=1}^k {w_{1i}+w_{2i}+w_{1i}-w_{1i}}
⇐ i = 1 ∑ k w 1 i + w 2 i = i = 1 ∑ k w 1 i + w 2 i + w 1 i − w 1 i
⇐ ∑ i = 1 k w 1 i + w 2 i = ∑ i = 1 k w 1 i + w 2 i \Leftarrow \sum_{i=1}^k {w_{1i}+w_{2i}}=\sum_{i=1}^k {w_{1i}+w_{2i}}
⇐ i = 1 ∑ k w 1 i + w 2 i = i = 1 ∑ k w 1 i + w 2 i
所以原结论成立。
∑ i = 1 n ∑ j = 1 m ∑ k = 1 p gcd ( i ⋅ j , i ⋅ k , j ⋅ k ) × gcd ( i , j , k ) × ( gcd ( i , j ) gcd ( i , k ) × gcd ( j , k ) + gcd ( i , k ) gcd ( i , j ) × gcd ( j , k ) + gcd ( j , k ) gcd ( i , j ) × gcd ( i , k ) ) \sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(i\cdot j,i\cdot k,j\cdot k)\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)
i = 1 ∑ n j = 1 ∑ m k = 1 ∑ p g cd( i ⋅ j , i ⋅ k , j ⋅ k ) × g cd( i , j , k ) × ( g cd( i , k ) × g cd( j , k ) g cd( i , j ) + g cd( i , j ) × g cd( j , k ) g cd( i , k ) + g cd( i , j ) × g cd( i , k ) g cd( j , k ) )
∑ i = 1 n ∑ j = 1 m ∑ k = 1 p g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) g c d ( i , j , k ) × gcd ( i , j , k ) × ( gcd ( i , j ) gcd ( i , k ) × gcd ( j , k ) + gcd ( i , k ) gcd ( i , j ) × gcd ( j , k ) + gcd ( j , k ) gcd ( i , j ) × gcd ( i , k ) ) \sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)
i = 1 ∑ n j = 1 ∑ m k = 1 ∑ p g c d ( i , j , k ) g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) × g cd( i , j , k ) × ( g cd( i , k ) × g cd( j , k ) g cd( i , j ) + g cd( i , j ) × g cd( j , k ) g cd( i , k ) + g cd( i , j ) × g cd( i , k ) g cd( j , k ) )
∑ i = 1 n ∑ j = 1 m ∑ k = 1 p g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) × ( gcd ( i , j ) gcd ( i , k ) × gcd ( j , k ) + gcd ( i , k ) gcd ( i , j ) × gcd ( j , k ) + gcd ( j , k ) gcd ( i , j ) × gcd ( i , k ) ) \sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p gcd(i , j)\cdot gcd(j , k) \cdot gcd(i,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)
i = 1 ∑ n j = 1 ∑ m k = 1 ∑ p g c d ( i , j ) ⋅ g c d ( j , k ) ⋅ g c d ( i , k ) × ( g cd( i , k ) × g cd( j , k ) g cd( i , j ) + g cd( i , j ) × g cd( j , k ) g cd( i , k ) + g cd( i , j ) × g cd( i , k ) g cd( j , k ) )
∑ i = 1 n ∑ j = 1 m ∑ k = 1 p g c d ( i , j ) 2 ⋅ g c d ( j , k ) 2 ⋅ g c d ( i , k ) 2 \sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p gcd(i , j)^2 \cdot gcd(j , k)^2 \cdot gcd(i,k)^2
i = 1 ∑ n j = 1 ∑ m k = 1 ∑ p g c d ( i , j ) 2 ⋅ g c d ( j , k ) 2 ⋅ g c d ( i , k ) 2
p × ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) 2 + n × ∑ i = 1 m ∑ j = 1 p g c d ( i , j ) 2 + m × ∑ i = 1 n ∑ j = 1 p g c d ( i , j ) 2 p \times \sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2+n \times \sum_{i=1}^m\sum_{j=1}^p gcd(i,j)^2+m \times \sum_{i=1}^n\sum_{j=1}^p gcd(i,j)^2
p × i = 1 ∑ n j = 1 ∑ m g c d ( i , j ) 2 + n × i = 1 ∑ m j = 1 ∑ p g c d ( i , j ) 2 + m × i = 1 ∑ n j = 1 ∑ p g c d ( i , j ) 2
现在只需要处理出 ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) 2 \sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2 ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) 2 ,就可以用三次反演解决。
令 s = m i n ( n , m ) s = min(n,m) s = m i n ( n , m ) ,
∑ i = 1 n ∑ j = 1 m g c d ( i , j ) 2 \sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2
i = 1 ∑ n j = 1 ∑ m g c d ( i , j ) 2
∑ k = 1 s k 2 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = k ] \sum_{k=1}^{s}k^2\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=k]
k = 1 ∑ s k 2 i = 1 ∑ n j = 1 ∑ m [ g c d ( i , j ) = k ]
∑ k = 1 s k 2 ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ g c d ( i , j ) = 1 ] \sum_{k=1}^{s}k^2\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i,j)=1]
k = 1 ∑ s k 2 i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ [ g c d ( i , j ) = 1 ]
∑ k = 1 s k 2 ∑ d = 1 ⌊ s k ⌋ μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ \sum_{k=1}^{s}k^2 \sum_{d=1}^{\lfloor \frac{s}{k} \rfloor } \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
k = 1 ∑ s k 2 d = 1 ∑ ⌊ k s ⌋ μ ( d ) ⌊ k d n ⌋ ⌊ k d m ⌋
∑ k = 1 s ∑ d = 1 ⌊ s k ⌋ k 2 μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ \sum_{k=1}^{s}\sum_{d=1}^{\lfloor \frac{s}{k} \rfloor } k ^2 \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
k = 1 ∑ s d = 1 ∑ ⌊ k s ⌋ k 2 μ ( d ) ⌊ k d n ⌋ ⌊ k d m ⌋
∑ k = 1 s ∑ k d = 1 s k 2 μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ \sum_{k=1}^{s}\sum_{kd=1}^{s} k ^2 \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
k = 1 ∑ s k d = 1 ∑ s k 2 μ ( d ) ⌊ k d n ⌋ ⌊ k d m ⌋
令 T = k d T=kd T = k d ,
∑ T = 1 s ∑ k ∣ T k 2 μ ( T k ) ⌊ n T ⌋ ⌊ m T ⌋ \sum_{T=1}^{s}\sum_{k|T} k^2 \mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor
T = 1 ∑ s k ∣ T ∑ k 2 μ ( k T ) ⌊ T n ⌋ ⌊ T m ⌋
∑ T = 1 s f ( T ) ⌊ n T ⌋ ⌊ m T ⌋ \sum_{T=1}^{s}f(T)\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor
T = 1 ∑ s f ( T ) ⌊ T n ⌋ ⌊ T m ⌋
其中 f ( n ) = ∑ k ∣ n k 2 μ ( n k ) f(n)=\sum_{k|n} k^2 \mu(\frac{n}{k}) f ( n ) = ∑ k ∣ n k 2 μ ( k n ) , 由卷积的性质得该函数为积性函数,考虑如何用线性筛求出其前缀和。
如果 p p p 是一个质数,那么有:
f ( p ) = 1 2 × μ ( p ) + p 2 × μ ( 1 ) = p 2 − 1 f(p)=1^2 \times \mu(p)+p^2 \times \mu(1)=p^2-1
f ( p ) = 1 2 × μ ( p ) + p 2 × μ ( 1 ) = p 2 − 1
f ( p k ) = ∑ i = 0 k p 2 i × μ ( p k − i ) f(p^k)=\sum_{i=0}^k p^{2i} \times \mu(p^{k-i})
f ( p k ) = i = 0 ∑ k p 2 i × μ ( p k − i )
又因为当 k − i ≥ 2 k-i \ge 2 k − i ≥ 2 时,μ ( p k − i ) = 0 \mu(p^{k-i})=0 μ ( p k − i ) = 0 ,所以所有有贡献的 i > k − 2 i > k - 2 i > k − 2 , 即 i = k i=k i = k 或 i = k − 1 i=k-1 i = k − 1 。
f ( p k ) = p 2 k − p 2 ( k − 1 ) = ( p 2 − 1 ) p 2 ( k − 1 ) = f ( p ) p 2 ( k − 1 ) f(p^k)=p^{2k}-p^{2(k-1)}=(p^2-1)p^{2(k-1)}=f(p)p^{2(k-1)}
f ( p k ) = p 2 k − p 2 ( k − 1 ) = ( p 2 − 1 ) p 2 ( k − 1 ) = f ( p ) p 2 ( k − 1 )
观察发现括号内 p p p 减少了 k − 1 k-1 k − 1 次方,系数增加 p 2 ( k − 1 ) p^{2(k-1)} p 2 ( k − 1 )
所以 f ( p k ) = f ( p k − 1 ) × p 2 f(p^k)=f(p^{k-1}) \times p^2 f ( p k ) = f ( p k − 1 ) × p 2
整理一下得:
f ( i × p r i m e [ j ] ) = { f ( i ) × f ( p r i m e [ j ] ) ( i , p r i m e [ j ] ) = 1 f ( i ) × p r i m e [ j ] 2 ( i , p r i m e [ j ] ) = 1 f(i \times prime[j])=\begin{cases}
f(i) \times f(prime[j]) & (i,prime[j])=1 \\\\
f(i) \times prime[j]^2 & (i,prime[j])\not=1
\end{cases}
f ( i × p r i m e [ j ] ) = ⎩ ⎪ ⎨ ⎪ ⎧ f ( i ) × f ( p r i m e [ j ] ) f ( i ) × p r i m e [ j ] 2 ( i , p r i m e [ j ] ) = 1 ( i , p r i m e [ j ] ) = 1
复杂度Θ ( n + t n ) \Theta(n+t\sqrt n) Θ ( n + t n )
#include <cstdio>
#include <iostream>
using namespace std;
#define Mod 1000000007
template<typename _T>
void Read( _T &x ) {
x = 0; int f = 1;
char s = getchar( );
for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
template<typename _T>
void Write( _T x ) {
if( x < 0 ) putchar('-') , x = -x;
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + '0' );
}
const int MAXN = 20000000;
int t , n , m , p , k , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
f[ i ] = ( 1ll * i * i - 1 ) % Mod;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
f[ i * prime[ j ] ] = 1ll * f[ i ] * prime[ j ] % Mod * prime[ j ] % Mod;
break;
}
f[ i * prime[ j ] ] = 1ll * f[ i ] * f[ prime[ j ] ] % Mod;
}
}
for( int i = 2 ; i <= MAXN ; i ++ )
f[ i ] = ( f[ i ] + f[ i - 1 ] ) % Mod;
}
int solve( int n , int m ) {
int d = min( n , m ) , Ans = 0;
for( int l = 1 , r ; l <= d ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * ( n / l ) % Mod * ( m / l ) % Mod ) % Mod;
}
return Ans;
}
int main( ) {
sieve( );
Read( t );
while( t -- ) {
Read( n ) , Read( m ) , Read( p );
int Ans = ( 1ll * n * solve( m , p ) % Mod + 1ll * m * solve( n , p ) % Mod + 1ll * p * solve( n , m ) % Mod ) % Mod;
Write( Ans ) , putchar('\n');
}
return 0;
}